Referring to the drawings, FIG. 1 (PRIOR ART) depicts a typical system 100 for encoding and decoding data. Original information (typically, digital data) from a source is encoded using an encoder 102 and transmitted over a communication channel (or stored on a storage device) 104. It is assumed that like all practical systems, the transmission channel is noisy (or the storage medium has errors), and this channel noise causes symbol errors in the words received at the end of the transmission channel. A symbol error is said to occur if any one or more bits in a symbol (for example, a byte) are wrong. The data so transmitted (or stored) is thereafter retrieved and decoded using a decoder 106 to reproduce the original information.
To ensure accurate storage, retrieval and transmission of data, a robust mechanism for checking and correcting errors is needed. Original information may be corrupted when it is transmitted or stored for subsequent retrieval. Sources of corruption in data include a noisy transmission channel, a scratch on a digital storage device such as a compact disk, and the like. The number of symbols any two code words are separated is called the “distance,” or, more commonly, the Hamming distance, between the two code words. A common measure of the error-correcting capability of a system is the minimum distance dmin between valid code words.
It is well known that adding redundant information to data can help ensure accuracy of stored or transmitted information. Every k-symbol block of code word can be encoded into an n-symbol block (n>k) by adding n-k redundant symbols. The simplest error-correcting code is simply to repeat everything several times and then use a majority vote or other method to recover the original information from the corrupted data. But this “brute force” information recovery method does not achieve the goal of a high-speed, high-density information processing system.
Channel errors can occur at randomly isolated locations or in localized finite-length sequences. The latter are known as burst errors. A sequence of burst errors may affect many symbols in one code word and cause the decoder to fail to retrieve the original information from a corrupted code word. In J. Chen and P. Owsley, “A burst-error-correcting algorithm for Reed-Solomon Codes,” IEEE Trans. on Information Theory, vol. 38, no. 6, November 1992, at pp. 1807-12 an algorithm for correcting burst errors was presented, but it is effective only for correcting a single burst in each code word.
A more efficient technique, known as interleaving, can be used to extend the capability of linear block codes. In this technique, several code words are generated simultaneously and stored in a memory matrix row-wise. These code words are then transmitted across a channel column-wise. In this way, a burst of symbol errors is distributed among multiple received words and a fewer errors occur in each received word. FIG. 2 illustrates an 8-bit interleaved system, where each row corresponds to one code word and the code word matrix is transmitted column-wise. In this example, a burst error across 11 symbols (shown shaded in the figure) is spread such that it causes maximally 2 symbol errors in each received word.
Reed-Solomon (RS) codes is helpful in correcting burst errors, where a series of bits in a code word are received in error. The advantage with RS codes is that they provide a high coding gain at a high code rate (k/n). This means that an RS decoder can recover from more errors with less redundant symbols. Stated alternatively, RS codes allow a target Bit Error Ratio (BER) to be achieved with a lower transmitter output power. RS codes were first proposed in a classic 1960 paper entitled “Polynomial Codes over Certain Finite Fields” by Irving S. Reed and Gustave Solomon. RS codes are based on a specialist area of mathematics known as finite fields or Galois fields. They are a subset of BCH codes and are linear block codes with a wide range of applications in digital communications—wireless or mobile communications including cellular telephones, microwave links, satellite communications, digital television, high-speed modems (ADSL, xDSL)—and storage systems including compact disk, DVD, bar codes and others.
Interleaved RS decoders have been found to be useful in satellite and optical communication systems as well as in storage applications. When interleaving is used, it is very likely that received words in one interleaving block have the same error locations. This observation was used in a method presented in V. Y. Krachkovsky and Y. X. Lee, “Decoding for Iterative Reed-Solomon Coding Schemes,” IEEE Trans. on Magnetics, vol. 33, no. 5, September 1997, pp. 2740-42 (“Krachkovsky et al.”), where all check symbols in each row code are combined to find a “covering error locator polynomial” that covers all possible error locations in every code word.
In systems where burst errors are common there is a demand for large coding gain and a very small tolerance for increase in hardware complexity. Accordingly, there is a need for an improvement in the art.